#include <string.h>
#include <iostream>
#include <fstream>
#include <sstream>
#include <list>
#include <unordered_map>

using namespace std;

class LRUCache{
public:
    LRUCache(int capacity)
    :_capacity(capacity)
    {

    }

    void put(int key,int value){
        //key存在
        auto it = _cache.find(key);
        if(it != _cache.end()){
            //更新元素
            it->second->second = value;
            _list.splice(_list.begin(),_list,it->second);
            return;
        }

        //key不存在，判断容量
        if(_list.size() == _capacity){
            auto last = _list.back();
            _cache.erase(last.first);
            _list.pop_back();
        } 
        _list.push_front({key,value});
        _cache[key] = _list.begin();
    }

    int  get(int key){
        auto it = _cache.find(key);
        if(it == _cache.end()){
            return -1;
        }
        _list.splice(_list.begin(),_list,it->second);
        return it -> second -> second;
    }

    void display(){
        for(auto it = _list.begin();it != _list.end(); ++it){
            cout << "(" << it->first << ","
                << it->second << ")";
        }
        cout << endl;
    }
private:
    int _capacity;
    list<pair<int,int>> _list;
    unordered_map<int,list<pair<int,int>>::iterator> _cache;
};


void test(){
    LRUCache lru(2);
    lru.put(1,20);
    lru.display();
    lru.put(2,90);
    lru.display();
    cout << lru.get(2) << endl;
    lru.display();
    lru.put(3,100);
    cout << lru.get(3) << endl;
    lru.display();
}

int main()
{
    test();
    return 0;
}

